package _dp

import org.junit.Assert
import org.junit.Test


/**
 * 题型：动态规划 / 分治法 / 贪心算法
 *
 * https://blog.csdn.net/2401_86968005/article/details/152666954
 * https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
 * https://leetcode.cn/problems/maximum-subarray/description/
 *
 * 53. 最大子数组和

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
 */
class leetcode_53 {
    @Test
    fun test_1() {
        val actual = maxSubArray(intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4))
        val expect = 6
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_2() {
        val actual = maxSubArray(intArrayOf(1))
        val expect = 1
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_3() {
        val actual = maxSubArray(intArrayOf(5, 4, -1, 7, 8))
        val expect = 23
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_170() {
        val actual = maxSubArray(intArrayOf(-2, 1))
        val expect = 1
        Assert.assertEquals(actual, expect)
    }

    private fun maxSubArray(nums: IntArray): Int {
        /**
         * 动态规划
         *
         * 思路：
         * dp[i]，表示以 nums[i] 结尾的连续子数组的最大和.
         * dp[i] = max(nums[i], dp[i-1] + nums[i])
         * 全局最大值：dp 数组中的最大值就是整个数组的最大子数组和。
         *
         *
         * 空间优化后，
         * maxSum / currentSum = nums[0]
         * 要么延续之前的子数组继续累加，要么从当前元素开始新的子数组
         * currentSum = Math.max(nums[i], nums[i] + currentSum)
         * maxSum = Math.max(maxSum, currentSum)
         */
        return maxSubArray1(nums)
//        return maxSubArray2(nums)
    }

    private fun maxSubArray1(nums: IntArray): Int {
        val dp: IntArray = IntArray(nums.size) // dp[i]，表示以 nums[i] 结尾的连续子数组的最大和.
        dp[0] = nums[0]
        for (i in 1 until nums.size) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
        }
        // 全局最大值：dp 数组中的最大值就是整个数组的最大子数组和。
        return dp.max()
    }

    private fun maxSubArray2(nums: IntArray): Int {
        // 动态规划 (空间优化)
        var maxSum: Int = nums[0] // 最大和
        var currentSum: Int = nums[0] // 当前子数组的和

        for (i in 1 until nums.size) {
            // 要么延续之前的子数组继续累加，要么从当前元素开始新的子数组
            currentSum = Math.max(nums[i], nums[i] + currentSum)

            // 更新全局最大值
            maxSum = Math.max(maxSum, currentSum)
        }
        return maxSum
    }
}